Reflections on Trusting Trust

参考 Reflections on Trusting Trust，Running the “Reflections on Trusting Trust” Compiler。

The moral is obvious. You can’t trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code.

步骤一

如何编写一个自我复制程序（Quine）？使用 Java 编写的代码如下，还是有点难的。最开始想直接打印，但是打印语句需要包含完整的程序，而完整的程序又包含打印语句，是一个循环依赖的过程。要把循环解开，就只能在字符串中包含基本的行，经过特殊处理得到正确的输出，最简单的方式是使用占位符。似乎不能使用转义字符，因为反斜杠在字符串中也需要转义，所以根本没办法打印出相同的行。更短的示例可以参考 Quine Programs。

public class Main {
    public static void main(String[] args) {
        char n = 10;
        String t = new String(new char[]{'"', '"', '"'});
        String s = """
public class Main {
    public static void main(String[] args) {
        char n = 10;
        String t = new String(new char[]{'"', '"', '"'});
        String s = %s;
        System.out.printf(s, t + n + s + t);
    }
}
""";
        System.out.printf(s, t + n + s + t);
    }
}

步骤二

如何构建一个自编译的编译器（即由要编译的语言编写的编译器），是一个先有鸡还是先有蛋的问题，解决方案是引导（Bootstrapping）。简单来说，首先使用机器支持的语言编写编译器 A 的源代码，编译器 A 可以编译目标语言的子集。然后使用目标语言的子集编写编译器 B 的源代码，经过编译器 A 编译得到编译器 B 的二进制文件。之后就可以不断重复，得到支持完整目标语言的编译器。

if (c == 'v') return 11; // 旧编译器可以识别
if (c == 'v') return '\v'; // 新编译器才能识别

论文提到的例子是，在目标语言中添加 \v 符号，表示垂直制表符。由于旧编译器不识别该符号，所以使用垂直制表符的 ASCII 码 11 扩展旧编译器的源代码，旧编译器编译扩展后的源代码得到新编译器，新编译器就能够识别 \v 符号。

步骤三

修改编译器，以匹配指定模式，如果匹配则错误地编译源代码，这是特洛伊木马（Trojan horse）。可以在编译器中插入指定的匹配模式（后门，backdoor），使其匹配 login 命令的源代码。如果用户使用该编译器编译 login 命令，则命令会被错误编译，从而可以使用指定的密码登录系统的任意用户。

最关键的是，如果再添加一个针对编译器自身的匹配模式，在识别到当前正在编译编译器时，将特洛伊木马插入到新编译器中，则可以实现类似步骤二中的“学习”过程。也就是说，即使编译器 B 的源代码是正确的，使用包含以上两个匹配模式的编译器 A 编译，得到的编译器 B 的二进制文件依然包含两个特洛伊木马。最终，编译器 B 仍会错误地编译 login 命令，而编译器 B 的源代码却是正确的。

论文提到，将特洛伊木马插入到新编译器中，使用的是步骤一的自我复制程序。我看半天才理解这句话，可以这么想，特洛伊木马需要获取自身的代码，然后插入到新编译器的特定位置，类似自我复制需要输出自身的代码。